package com.togo.algorithm.medium.tree;

import com.togo.algorithm.common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author taiyn
 * @Description 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 * <p>
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 示例 1
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 * <p>
 * 示例 2:
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 * @Date 上午9:41 2022/4/16
 **/
public class Offer07 {
    int[] preorder;
    int[] inorder;
    Map<Integer, Integer> dic = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (preorder == null || preorder.length == 0) return null;
        if (preorder.length == 1) return new TreeNode(preorder[0]);

        for (int i = 0; i < inorder.length; i++) {
            dic.put(inorder[i], i);
        }

        this.preorder = preorder;
        this.inorder = inorder;

        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int pS, int pE, int iS, int iE) {
        if (pS > pE || iS > iE) return null;
        TreeNode head = new TreeNode(preorder[pS]);

        int indexOfpS = dic.get(preorder[pS]);

        head.left = build(pS + 1, pS + indexOfpS - iS, iS, indexOfpS - 1);
        head.right = build(pS + indexOfpS - iS + 1, pE, indexOfpS + 1, iE);

        return head;
    }

    public static void main(String[] args) {

    //[3,9,20,15,7]
        //[9,3,15,20,7]
        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};

        Offer07 offer07 = new Offer07();
        offer07.buildTree(preorder, inorder);
    }
}
